﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AnimEditor
{
  public class FTextureLayoutNode
	{
		public FTextureLayoutNode ChildA = null;
		public FTextureLayoutNode ChildB = null;
		public int MinX;
		public int MinY;
    public int SizeX;
		public int SizeY;
		public bool	Used;

		public FTextureLayoutNode(int InMinX,int InMinY,int InSizeX,int InSizeY)
		{
			MinX = InMinX;
			MinY = InMinY;
			SizeX = InSizeX;
			SizeY = InSizeY;
			Used  = false;
    }
	}

  public class FTextureLayout
  {
    int mSizeX;
	  int mSizeY;
	  bool PowerOfTwoSize;
    char[] GLogs = new char[257];
	  List<FTextureLayoutNode> Nodes = new List<FTextureLayoutNode>();

	  /**
	   * Minimal initialization constructor.
	   * @param	MinSizeX - The minimum width of the texture.
	   * @param	MinSizeY - The minimum height of the texture.
	   * @param	MaxSizeX - The maximum width of the texture.
	   * @param	MaxSizeY - The maximum height of the texture.
	   * @param	InPowerOfTwoSize - True if the texture size must be a power of two.
	   */
	  public FTextureLayout(int MinSizeX,int MinSizeY,int MaxSizeX,int MaxSizeY,bool InPowerOfTwoSize)
    {
      SizeX = MinSizeX;
      SizeY = MinSizeY;
      PowerOfTwoSize = InPowerOfTwoSize;
      Nodes.Add(new FTextureLayoutNode(0,0,MaxSizeX,MaxSizeY));

      for( int i=0,e=-1,c=0; i<=256; i++ )
	    {
		    GLogs[i] = (char)(e+1);
		    if( i==0 || ++c>=(1<<e) )
		    {
          c = 0;
          e++;
		    }
	    }
    }

    char appCeilLogTwo(uint Arg)
    {
      if (--Arg == 0xffffffff)
      {
        return (char)0;
      }
      char Shift = (char)(Arg <= 0x10000 ? (Arg <= 0x100 ? 0 : 8) : (Arg <= 0x1000000 ? 16 : 24));
      return (char)(Shift + GLogs[Arg >> Shift]);
    }

	  /**
	   * Finds a free area in the texture large enough to contain a surface with the given size.
	   * If a large enough area is found, it is marked as in use, the output parameters OutBaseX and OutBaseY are
	   * set to the coordinates of the upper left corner of the free area and the function return true.
	   * Otherwise, the function returns false and OutBaseX and OutBaseY remain uninitialized.
	   * @param	OutBaseX - If the function succeedes, contains the X coordinate of the upper left corner of the free area on return.
	   * @param	OutBaseY - If the function succeedes, contains the Y coordinate of the upper left corner of the free area on return.
	   * @param	ElementSizeX - The size of the surface to allocate in horizontal pixels.
	   * @param	ElementSizeY - The size of the surface to allocate in vertical pixels.
	   * @return	True if succeeded, false otherwise.
	   */
	  public bool AddElement(out int OutBaseX,out int OutBaseY,int ElementSizeX,int ElementSizeY)
	  {
		  // Pad to 4 to ensure alignment
		  ElementSizeX = (ElementSizeX + 3) & ~3;
		  ElementSizeY = (ElementSizeY + 3) & ~3;

		  // Try allocating space without enlarging the texture.
      FTextureLayoutNode node = AddSurfaceInner(null, ElementSizeX, ElementSizeY, false);
      if (node == null)
		  {
			  // Try allocating space which might enlarge the texture.
        node = AddSurfaceInner(null, ElementSizeX, ElementSizeY, true);
		  }

      if (node != null)
		  {
        node.Used = true;
        OutBaseX = node.MinX;
        OutBaseY = node.MinY;
			  if(PowerOfTwoSize)
			  {
          SizeX = Math.Max(SizeX, 1 << appCeilLogTwo((uint)(node.MinX + ElementSizeX)));
          SizeY = Math.Max(SizeY, 1 << appCeilLogTwo((uint)(node.MinY + ElementSizeY)));
			  }
			  else
			  {
          SizeX = Math.Max(SizeX, node.MinX + ElementSizeX);
          SizeY = Math.Max(SizeY, node.MinY + ElementSizeY);
			  }
			  return true;
		  }
		  else
		  {
        OutBaseX = 0;
        OutBaseY = 0;
			  return false;
		  }
	  }

	  /**
	   * Returns the minimum texture width which will contain the allocated surfaces.
	   */
    public int SizeX
    {
      get{ return mSizeX; }
      set{ mSizeX = value; }
    }

	  /**
	   * Returns the minimum texture height which will contain the allocated surfaces.
	   */
    public int SizeY
    {
      get{ return mSizeY; }
      set{ mSizeY = value; }
    }

	  public FTextureLayoutNode AddSurfaceInner(FTextureLayoutNode Node,int ElementSizeX,int ElementSizeY,bool AllowTextureEnlargement)
	  {
      if(Node==null)
      {
        Node = Nodes[0];
      }

		  if(Node.ChildA != null)
		  {
			  FTextureLayoutNode	Result = AddSurfaceInner(Node.ChildA,ElementSizeX,ElementSizeY,AllowTextureEnlargement);
			  if(Result != null)
				  return Result;
			  return AddSurfaceInner(Node.ChildB,ElementSizeX,ElementSizeY,AllowTextureEnlargement);
		  }
		  else
		  {
			  if(Node.Used)
				  return null;

			  if(Node.SizeX < ElementSizeX || Node.SizeY < ElementSizeY)
				  return null;

			  if(!AllowTextureEnlargement)
			  {
				  if(Node.MinX + ElementSizeX > SizeX || Node.MinY + ElementSizeY > SizeY)
				  {
					  // If this is an attempt to allocate space without enlarging the texture, and this node cannot hold the element
					  // without enlarging the texture, fail.
					  return null;
				  }
			  }

			  if(Node.SizeX == ElementSizeX && Node.SizeY == ElementSizeY)
				  return Node;

			  int	ExcessWidth = Node.SizeX - ElementSizeX;
				int ExcessHeight = Node.SizeY - ElementSizeY;

			  if(ExcessWidth > ExcessHeight)
			  {
				  Node.ChildA = new FTextureLayoutNode(Node.MinX,Node.MinY,ElementSizeX,Node.SizeY);
          Nodes.Add(Node.ChildA);

				  Node.ChildB = new FTextureLayoutNode(Node.MinX + ElementSizeX,Node.MinY,Node.SizeX - ElementSizeX,Node.SizeY);
				  Nodes.Add(Node.ChildB);
			  }
			  else
			  {
				  Node.ChildA = new FTextureLayoutNode(Node.MinX,Node.MinY,Node.SizeX,ElementSizeY);
          Nodes.Add(Node.ChildA);

				  Node.ChildB = new FTextureLayoutNode(Node.MinX,Node.MinY + ElementSizeY,Node.SizeX,Node.SizeY - ElementSizeY);
          Nodes.Add(Node.ChildB);
			  }

			  return AddSurfaceInner(Node.ChildA,ElementSizeX,ElementSizeY,AllowTextureEnlargement);
		  }
	  }
  }
}
